A hashing function is a function that transforms a key value into a table index. The table index is often referred to as a hash value. The key value typically contains more bits than the table index.
As applied to a memory, an incoming datum contains a key value, the memory is the table, and the memory address where the incoming datum is stored is the table index. The table index can be the key value, or a hash value generated by a hashing function. A smaller table can be used when the table index is a hash value, since the hash value has fewer bits than the key value. When the table index is generated by a hashing function, multiple key values will map onto a single table index. This is known as a hash collision. Two prior art solutions to accommodate hash collisions include open chaining and closed chaining.
In an open chaining scheme, each location in the memory may be a data structure, such as a linked list, that is capable of storing multiple entries. When a hash collision occurs, all entries with the same table index are stored in the same data structure (e.g., in the same linked list). Conceptually, open chaining results in a memory that is a set of lists. To retrieve the data, all the entries in the list for a particular hash value have to be searched. If the list is large, the search may be very time consuming.
In a closed chaining scheme, when a hash collision occurs the incoming data causing the collision is stored in an entry in the memory that is subsequent to the location to which the key value hashed. This subsequent entry may be the next sequential memory location or may be the next location available sequentially after all other locations currently storing information that is associated with a hash value to the same location or all other locations already being used. To retrieve the information, the memory must be searched from the location corresponding to the table index to the next empty entry in the memory to determine whether that particular entry exists in the memory. Therefore, in large or frequently changing memories, retrieval of data can become time consuming as it is possible that a large portion of a memory may have to be searched.
Memories are often used with bridges in a communication network to store addresses of local devices. By storing the addresses of local devices, the bridge can determine whether to forward packets of information onto other parts of the network, an event which may waste resources and is undesirable. Such a bridge checks the destination address of the packet with previous source addresses stored in its memory to determine the destination address is local to the bridge. If so, the bridge need not forward the packet to other parts of the network, so that part of the network doesn't have to perform the unnecessary function of transmitting a packet whose recipient is on another portion of the network.
One way to reduce the size of these bridging devices is to reduce the size of their memory. However, reduction in the size of the memory may cause some of the same problems discussed above with respect to hashing as given above. Another way to improve the performance of these bridges is to store and retrieve addresses more quickly.
What is needed is an improved memory management strategy for use in memories that store and retrieve information based on hash values.